package algorithm.leetcode.I101to200;

import algorithm.leetcode.ListNode;

/**
 * 找到两个单链表相交的起始节点
 * 不相交则返回null
 *
 * 思路: 先计算两个链表的长度,再快慢指针
 */

public class Q160 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        // 第一步:计算两个链表的长度
        int lengthA = headA == null ? 0 : 1;
        int lengthB = headB == null ? 0 : 1;
        ListNode currA = headA, currB = headB;

        while (currA != null || currB != null) {
            if (currA != null) {
                currA = currA.next;
                lengthA++;
            }
            if (currB != null) {
                currB = currB.next;
                lengthB++;
            }
        }

        // 第二步:两个链表尾端对齐
        currA = headA;
        currB = headB;
        while (lengthA > lengthB) {
            lengthA--;
            currA = currA.next;
        }
        while (lengthB > lengthA) {
            lengthB--;
            currB = currB.next;
        }

        // 第三步:找相交点,并且是引用相同
        while (currA != null && currB != null) {
            if (currA == currB) return currA;
            currA = currA.next;
            currB = currB.next;
        }
        return currA;
    }

}
